#include "Configurator.h"
#include <list>
#include <vector>
#include <algorithm>

#ifndef SOLVER_H_
#define SOLVER_H_

using namespace std;

typedef struct Cycle {
    int StartNode;   // First city in the cycle
    int Length;      // Total # cities
    int FreeLength;  // # cities not in the Include list
	bool operator<(struct Cycle &b) { return Length < b.Length; }
} Cycle;

class AssignmentProblem {
private:
    static const int infinity = MAXINT;

    // Problem definition
    int cityCount;                          // count of points
    int** distances;                       // square matrix of distances between all points

    int* constraintMap;
    // constraintMap[i] >  0 -> (i, constraintMap[i]-1) is Included
    // constraintMap[i] == 0 -> no constraints on (i, ?)
    // constraintMap[i] <  0 -> -1 - constraintMap[i] = index of first element in exclusions list.
    int* exclusions;
    // See constraintMap. List is terminated by -1.
	int exclusionsCount;
	int exclusionsLength;

	// Parent problem
    AssignmentProblem *parent;
    int childIndex;
	AssignmentProblem(AssignmentProblem *parent, int index);

	// Solution:
	// Assignment problem
    int* toCities;               // destination city
    int* fromCities;             // originating city
    long lowerBound;             // lower bound from assignment problem
	// Patched problem
	int* patchedToCities;		// destination city
    int* patchedFromCities;     // originating city

    // Dual variables
    int* u;
    int* v;

public:
    AssignmentProblem(int cityCount, int** distances);
	~AssignmentProblem();

    long getLowerBound() const { return lowerBound; }
    long getParentLowerBound() { return parent == NULL ? infinity : parent->lowerBound; }
    int* GetCities();

    long Solve(); 

    int AssignmentProblem::getCycleCount() const { return cycles.size(); }
    int AssignmentProblem::getChildCount() const { return cycles[minCycle].FreeLength; }

	long Patch(long upperBound);
    
	bool operator<(AssignmentProblem const &y);
	void GenerateSubproblems(list<AssignmentProblem*> &problemList);

private:
    bool IsAllowed(int row, int column);
    bool IsAllowedConstraint(int value, int column);
    void Include(int from, int to);
	void Exclude(int from, int to);
    void AddConstraints();
    bool SolveFromScratch();
    bool SolveIncremental();

    // We keep these as instance variables
    int* pathOrigins;
    int* reducedCosts;
    int* labeledRow;
    int* unlabeledColumn;
	void Dump(int* a);
    void AllocateAugmentingPathTemporaries();
    void FreeAugmentingPathTemporaries();
    void FindAugmentingPath(int row);

	std::vector<Cycle> cycles;
    int minCycle;

    void ComputeCycles();

    void Patch(int from, int to, int from2, int to2);
    long Patch(int startCity, int startCity2);

    int* childFromCities;
    int* childToCities;

	// Reference counting
private:
	int refCount;
public:
	void IncrementRefCount();
	bool DecrementRefCount();
};

class Solver
{
public:
	Solver(Configurator *configurator);
	int Solve();
	void Finish(double time);
	
private:
	Configurator* dwarfConfigurator;
	long totalNodes;

	void ArrayDestroyer(int **arrayForDel, int dimension);

    int cityCount;                           // count of points
    int **distances;                         // square matrix of distances between all points
    static const int infinity = MAXINT;
    long upperBound;
    list<AssignmentProblem*> problemList;
    list<AssignmentProblem*> solvedList;

    AssignmentProblem *best;

    void AddSolvedProblem(AssignmentProblem *problem);
    AssignmentProblem *NextSolvedProblem();
};

#endif
